package algorithm.recursionAndbacktrack.p93;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 93. 复原 IP 地址
 */
public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ips = new ArrayList<>();
        restoreIpAddress(s, 0, ips, new ArrayDeque<>());
        return ips;
    }

    private void restoreIpAddress(String s, int startIndex, List<String> ips, ArrayDeque<Integer> ip) {
        if (ip.size() == 4) {
            if(startIndex == s.length()) {
                StringBuilder sb = new StringBuilder();
                Iterator<Integer> iterator = ip.iterator();
                for (int j = 0; j < 3; j++) {
                    sb.append(iterator.next() + ".");
                }
                sb.append(iterator.next());
                ips.add(sb.toString());
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (startIndex == s.length()) {
            return;
        }

        // 最多选3位
        for (int i = 1; i <= 3 && startIndex + i <= s.length(); i++) {
            String num_str = s.substring(startIndex, startIndex + i);
            int num = Integer.parseInt(num_str);
            // 1位就是0或者超过1位不能以0开头
            if ((num_str.equals("0") || !num_str.startsWith("0")) && num <= 255) {
                ip.addLast(num);
                restoreIpAddress(s, startIndex + i, ips, ip);
                ip.removeLast();
            }
        }
    }

    public static void main(String[] args) {
//        System.out.println(new Solution().restoreIpAddresses("25525511135"));
        System.out.println(new Solution().restoreIpAddresses("0000"));
    }
}